package java_core.array.Day5_13;

/*414. 第三大的数 https://leetcode-cn.com/problems/third-maximum-number/
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。*/
public class DiSanDaDeShu {
    public static void main(String[] args) {
        int[] arr = {5,2,2};
        System.out.println(thirdMax(arr));
    }
    private static long MIN = Long.MIN_VALUE;    // MIN代表没有在值
    public static int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else {
            int maxNumber = nums[0];
            long secondNumber = MIN;
            long thirdNumber = MIN;
            for (int i = 1; i < nums.length; i++) {
                if (maxNumber < nums[i]) {
                    thirdNumber = secondNumber;
                    secondNumber = maxNumber;
                    maxNumber = nums[i];
                } else if (secondNumber < nums[i] && nums[i] < maxNumber) {
                    thirdNumber = secondNumber;
                    secondNumber = nums[i];
                } else if (thirdNumber < nums[i] && nums[i] < secondNumber) {

                    thirdNumber = nums[i];
                }


            }

            if (thirdNumber != MIN) {

                return (int) thirdNumber;
            } else {
                return maxNumber;
            }

        }


    }

    class Solution {
        private long MIN = Long.MIN_VALUE;    // MIN代表没有在值

        public int thirdMax(int[] nums) {
            if (nums == null || nums.length == 0) throw new RuntimeException("nums is null or length of 0");
            int n = nums.length;

            int one = nums[0];
            long two = MIN;
            long three = MIN;

            for (int i = 1; i <  n; i++) {
                int now = nums[i];
                if (now == one || now == two || now == three) continue;    // 如果存在过就跳过不看
                if (now > one) {
                    three = two;
                    two = one;
                    one = now;
                } else if (now > two) {
                    three = two;
                    two = now;
                } else if (now > three) {
                    three = now;
                }
            }

            if (three == MIN) return one;  // 没有第三大的元素，就返回最大值
            return (int)three;
        }
    }


}
